import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/21 15:11
 * @description 记忆化DFS
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int[][] pre = {{0,1}, {1, 2}, {2, 3}, {3, 4}}, q = {{0,4}, {4, 0}, {1, 3}, {3, 0}};
        solution2.checkIfPrerequisite(5, pre, q);
    }

    public List<Boolean> checkIfPrerequisite( int numCourses, int[][] prerequisites, int[][] queries) {
        //有向无环图的逆邻接表
        LinkedList<Integer>[] inverseAdj = new LinkedList[numCourses];
        //每门课程的前置课程集合
        HashSet<Integer>[] map = new HashSet[numCourses];
        for (int i = 0; i < numCourses; i++) {
            inverseAdj[i] = new LinkedList<>();
            map[i] = new HashSet<>();
        }
        for (int[] prerequisite : prerequisites) {
            inverseAdj[prerequisite[1]].add( prerequisite[0] );
        }
        boolean[] visited = new boolean[numCourses];
        //递归查找每门课程的所有前置课程
        for (int i = 0; i < numCourses; i++) {
            if (!visited[i]) {
                dfs( i,inverseAdj,visited,map );
            }
        }
        List<Boolean> res = new ArrayList<>();
        //查找queries的前置关系
        for (int[] query : queries) {
            int from = query[0];
            int to = query[1];
            res.add( map[to].contains( from ) );
        }
        return res;
    }
    private static void dfs( int vertex, LinkedList<Integer>[] inverseAdj, boolean[] visited, HashSet<Integer>[] map ) {
        visited[vertex] = true;
        for (int i = 0; i < inverseAdj[vertex].size(); ++i) {
            int w = inverseAdj[vertex].get(i);
            if (!visited[w]){
                //如果之前没访问过 则递归查找w的所有前置课程
                dfs(w, inverseAdj, visited, map );
            }
            //将w和w的所有前置课程加入vertex的前置课程集合中
            map[vertex].add( w );
            map[vertex].addAll( map[w] );
        }
    }
}
